﻿//K个⼀组翻转链表（hard）:https://leetcode.cn/problems/reverse-nodes-in-k-group/
class Solution
{
public:
	ListNode* reverseKGroup(ListNode* head, int k)
	{
		// 1. 先求出需要逆序多少组
		int n = 0;
		ListNode* cur = head;
		while (cur)
		{
			cur = cur->next;
			n++;
		}
		n /= k;
		// 2. 重复 n 次：⻓度为 k 的链表的逆序即可
		ListNode* newHead = new ListNode(0);
		ListNode* prev = newHead;
		cur = head;
		for (int i = 0; i < n; i++)
		{
			ListNode* tmp = cur;
			for (int j = 0; j < k; j++)
			{
				ListNode* next = cur->next;
				cur->next = prev->next;
				prev->next = cur;
				cur = next;
			}
			prev = tmp;
		}
		// 把不需要翻转的接上
		prev->next = cur;
		cur = newHead->next;
		delete newHead;
		return cur;
	}
};